#include <iostream>
#include <map>

using namespace std;

// GOOG:
// Design a LRU (Last Recently Used) system with O(1) operations, e.g. Read / Write
// LRU: Evicting the element that has not been used for the longest period of time.

// Algorithm:
// Using a hashtable and doubly linked list to achieve O(1) on public operations:
//   T Read(long key)
//   Write(long key, T value)
//
// Storage:
//   Hashtable<long key, Node<T> *>
//   Node<T>(long key, T value>)     // store 'key' for deleting from hashtable in O(1)
//
template <class T>
class Node
{
public:
  Node<T> *previous, *next;
  pair<long, T> value;

  Node(long key, T v)
  {
    previous=next=null;
    value.first=key;
    value.second=v;
  }
};

template <class T>
class LRU
{
private:
  long size;
  Node<T> *head, *tail;
  map<long, Node<T>*> h;

  void Insert(Node<T> *p);
  void Update(Node<T> *p);
  void Evict();
public:
  LRU(long s)
  {
    if(s<=0) throw;
    head=tail=null;
    size=s;
  };

  T ReadByKey(long key);
  void Write(long key, T value);
};

template <class T>
T LRU<T>::ReadByKey(long key)
{
  Node<T> *p=h[key];
  if(!p)
  {
    return null;
  }
  else
  {
    Update(p);
    return p->value.second;
  }
}

template <class T>
void LRU<T>::Write(long key, T value)
{
  Node<T> *p=h[key];
  if(!p)
  {
    p=new Node<T>(key, value);
    h[key]=p;
    Insert(p);
  }
  else
  {
    p->value.second=value;
    Update(p);
  }
}

template <class T>
void LRU<T>::Insert(Node<T> *p)
{
  if(!head)
  {
    head=tail=p;
  }
  else
  {
    p->next=head;
    head->previous=p;
    head=p;
  }
  --size;
  if(size<0) Evict();
}

template <class T>
void LRU<T>::Evict()
{
  if(!tail) return;

  Node<T> *p=tail;
  if(head==tail)
  {
    head=tail=null;
  }
  else
  {
    tail=tail->previous;
    tail->next=null;
  }

  ++size;
  h.erase(p->value.first);
  delete p;
}

template <class T>
void LRU<T>::Update(Node<T> *p)
{
  if(p==head) return;
  if(p==tail)
  {
    tail=tail->previous;
    tail->next=null;
  }
  else
  {
    Node<T> *q=p->previous;
    q->next=p->next;
    q->next->previous=q;
  }

  p->previous=null;
  p->next=head;
  head->previous=p;
  head=p;
}

int main()
{
	// Sample Call: LRU<char> *cache=new LRU<char>(100);
	cout<<"Look source code for implement..."<<endl;
	return getchar();
}
